/*
 * @lc app=leetcode.cn id=128 lang=cpp
 * @lcpr version=30204
 *
 * [128] 最长连续序列
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {
        int n = nums.size();
        unordered_set<int> hashset(nums.begin(), nums.end());

        int maxNum = 0;
        for (auto e : hashset)
        {
            // 只有这个数前面的没有在数组里就可以开始计算它的连续子数组了
            // 这样就可以减去每个数重复计算的过程
            if (hashset.find(e - 1) == hashset.end())
            {
                int curNum = e;
                int curLength = 1;

                // 计算连续序列的长度
                while (hashset.find(curNum + 1) != hashset.end())
                {
                    curNum++;
                    curLength++;
                }
                maxNum = max(maxNum, curLength);
            }
        }
        return maxNum;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [100,4,200,1,3,2]\n
// @lcpr case=end

// @lcpr case=start
// [0,3,7,2,5,8,4,6,0,1]\n
// @lcpr case=end

// @lcpr case=start
// [1,0,1,2]\n
// @lcpr case=end

 */
